#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    bool flag = true;
    int lef = INT32_MIN;
    int rig = INT32_MAX;

    public:
    //中序遍历
    bool ans1(TreeNode* root){
        stack<TreeNode*> stack;
        long long inorder = (long long)INT32_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (root->val <= inorder) {
                return false;
            }
            inorder = root->val;
            root = root->right;
        }
        return true;
    }

};

TreeNode* createTree(vector<int>& num, int index, int len){
    if(num[index] == '#'){
        return NULL;
    }
    TreeNode* root = new TreeNode(num[index]);

    if(index * 2 + 1 < len){
        root->left = createTree(num, index * 2 + 1, len);
    }else{
        root->left = nullptr;
    }
    if(index * 2 + 2 < len){
        root->right = createTree(num, index * 2 + 2, len);
    }else{
        root->right = nullptr;
    }

    return root;
}


void test1(){
    vector<int> num = {2,1,3};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    bool ret = s.ans1(root);
    cout << ret << endl;
    
}

void test2(){
    vector<int> num = {5,1,4,'#','#',3,6};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    bool ret = s.ans1(root);
    cout << ret << endl;
    
}

void test3(){
    vector<int> num = {32,26,47,19,'#','#',56,'#',27};
    TreeNode* root = createTree(num, 0, num.size());

    Solution s;
    bool ret = s.ans1(root);
    cout << ret << endl;
    
}


int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();
    cout << "-----------------------------" << endl;
    test3();

    return 0;
}